COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	propos[f86,jmc]		Propositional goal achievement
C00005 ENDMK
C⊗;
propos[f86,jmc]		Propositional goal achievement

	The simplest class of problems of planning to achieve goals
comprises those in which situations are characterized by the values of a
collection of propositional variables and the actions are characterized by
their effects on the variables.  We can imagine that each action is
described by a joint assignment statement for all variables.  A goal
is a propositional expression in the variables, and it is achieved
by a finite sequence of actions.  Metaphysically, we don't need
preconditions, because we can presume that every action has some effect in
every situation.  Epistemologically, there may be a need for preconditions,
because it may be tedious to describe the effects of all actions in
all situations.

	The general case of propositional planning is surely NP complete,
and therefore it is necessary to concentrate attention on easier subcases.
We may also imagine that there is auxiliary information available.

[I was planning to use opening a safe as an example, but in opening as
safe one doesn't know the state.  This suggests expanding the problem
to include cases where one doesn't know the effects of all the actions
and can't fully observe the state].

Simplfication: Certain actions affect only certain variables; the
extreme is when the problem consists of independent subproblems.
Each variable has independent set and reset actions.

Let us assume that the state is observable, and the effects of
all actions are known.

What forms does partial knowledge take?

One meta-goal is to identify classes of problems that can be solved by
combining hill-climbing with short look-ahead.